﻿#include "stdafx.h"
#include "DailyTemperatures.h"

using namespace std;

namespace algorithm {
vector<int> CDailyTemperatures::Calc(vector<int>& temperatures)
{
    //单调栈,栈底->栈顶温度单调递减（可相等）
    using VecIndex = int;
    stack<VecIndex> cache;
    int size = (int)temperatures.size();
    vector<int> result(size, 0);

    for (VecIndex i = 0; i < size;) {
        if (cache.empty()) {
            cache.push(i);// 单调栈为空，直接将索引存入栈中
            i++; // 递增索引，继续判断下一个
            continue;
        }
        if (temperatures[cache.top()] >= temperatures[i]) {
            // 单调栈不为空，栈顶温度>=当前温度
            cache.push(i); // 直接将索引存入栈中
            i++; // 递增索引，继续判断下一个
            continue;
        }

        // 单调栈不为空，栈顶温度<当前温度，第一个大于栈顶温度的索引为i，i-cache.top()则表示第几天后的温度大于栈顶温度
        result[cache.top()] = i- cache.top();
        cache.pop(); // 弹出栈顶温度，不递增索引，继续判断栈顶与当前索引i的温度
    }
    return result;
}
}
